Content distributors (Google, Akamai, Limelight, Level3, etc.) preside over a multi-billion dollar business built on content delivery networks (CDNs), massively distributed networks of content caches. For example, in 2010 Akamai reported that its CDN had over 60,000 servers in 1,000 distinct networks spread over 70 countries. This growth is driven by an increase in demand for multimedia traffic and the use of mobile devices, resulting in a need to provide infrastructure that supports a good quality of experience for content consumers (e.g., low buffering times). It is expected that the demand for video and other multimedia traffic will continue to increase, as will the need for CDNs to deliver such traffic.
One of the building blocks of CDNs is the content caching algorithms that decide which content to cache, and when and where to cache it. Considerations of content caching algorithms include accuracy (how well they capture the content usage patterns) and complexity (how quickly they return an acceptable answer and how simple they are to realize). Conventional content caching algorithms rely on simple approaches such as least recently used (LRU), least frequently used (LFU) or first-in first-out (FIFO). These provide a simple, quick mechanism for deciding which content to cache, but are far from the optimal.
On the other hand, conventional solutions that have attempted to define an optimal solution have ended up being computationally prohibitive, and have been impracticable in real-world scenarios.